package com.beijing.demo.binarytree;

import java.util.Stack;

/**
 * 曹旭
 * 2025/5/11
 * 实现二叉树的三种序列遍历 :  不使用递归实现
 *  使用栈来辅助实现
 *  用一个栈完成后序遍历
 *  https://leetcode.cn/problems/binary-tree-postorder-traversal/
 *  用一个栈完成中序遍历
 *  https://leetcode.cn/problems/binary-tree-inorder-traversal/
 *  用一个栈完成先序遍历
 *  https://leetcode.cn/problems/binary-tree-preorder-traversal/
 */
public class BinaryTreeTraversalIteration {

    /**
     * 非递归二叉树   先序遍历
     * @param head
     */
    public static void preOrder(TreeNode head){
        if(head != null){
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(head);
            while(!stack.isEmpty()){
                TreeNode cur = stack.pop();
                System.out.print(cur.val + "   ");
                if(cur.right != null){
                    stack.push(cur.right);
                }
                if(cur.left != null){
                    stack.push(cur.left);
                }
            }
        }
    }


    /**
     * 二叉树非递归  中序遍历
     * @param head
     */
    public static void inOrder(TreeNode head){
        if(head != null){
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while(!stack.isEmpty() || head != null){
                if(head != null){
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.print(head.val + "  ");
                    head = head.right;
                }
            }
        }
    }

    /**
     * 用两个栈完成后续遍历
     * @param head
     */
    public static void posOrderTwoStacks(TreeNode head){
        if(head != null){
            Stack<TreeNode> stack = new Stack<TreeNode>();
            Stack<TreeNode> result = new Stack<TreeNode>();
            stack.push(head);
            while(!stack.isEmpty()){
                head = stack.pop();
                result.push(head);
                if(head.left != null){
                    stack.push(head.left);
                }
                if(head.right != null){
                    stack.push(head.right);
                }

            }
            while(!result.isEmpty()){
                System.out.print(result.pop().val + " ");
            }
        }
    }

    /**
     * 使用一个栈完成二叉树的后续遍历
     * @param h
     */
    public static void posOrderOneStacks(TreeNode h){
        if(h != null){
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(h);
            while(!stack.isEmpty()){
                TreeNode cur = stack.peek();
                if(cur.left != null && cur.left != h && cur.right != h){
                    stack.push(cur.left);
                } else if(cur.right != null && cur.right != h){
                    stack.push(cur.right);
                } else {
                    cur = stack.pop();
                    System.out.print(cur.val + "   ");
                    h = cur;
                }
            }
        }
    }





    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(7);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;
        t3.left = t6;
        t3.right = t7;
        posOrderOneStacks(t1);
    }
}
